package features.advance.leetcode.tree.medium;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.*;

/**
 *  剑指 Offer 32 - III. 从上到下打印二叉树 III
 *
 *  难度：中等
 *
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，
 * 第三行再按照从左到右的顺序打印，其他行以此类推。
 *
 *
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层次遍历结果：
 *
 * [
 *   [3],
 *   [20,9],
 *   [15,7]
 * ]
 *
 *
 * 提示：
 *
 * 节点总数 <= 1000
 *
 * @author LIN
 * @date 2021-06-21
 */
public class Offer32_3 {
    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public List<List<Integer>> levelOrder(TreeNode<Integer> root) {

                if(root == null){
                    return new ArrayList<>();
                }
                List<List<Integer>> list = new ArrayList<>();
                LinkedList<Integer> layer = new LinkedList<>();

                Deque<TreeNode<Integer>> queue = new LinkedList<>();

                queue.add(root);
                int layCount = 1;
                while(!queue.isEmpty()){
                    TreeNode<Integer> poll = queue.poll();
                    if(list.size() % 2 == 0){
                        layer.addLast(poll.val);
                    }else{
                        layer.addFirst(poll.val);

                    }
                    layCount--;
                    if(poll.left != null){
                        queue.add(poll.left);
                    }
                    if(poll.right != null){
                        queue.add(poll.right);
                    }
                    if(layCount == 0){
                        list.add(layer);
                        layer = new LinkedList<>();
                        layCount = queue.size();
                    }
                }
                return list;
            }
        };

        String str = "[3,9,20,4,6,15,7,1,2,9,2,null,null,null]";
        TreeNode<Integer> root = TreeUtil.stringToTreeNode(str);
        List<List<Integer>> lists = solution.levelOrder(root);
        System.out.println(lists);

    }


    static class Solution {
        public List<List<Integer>> levelOrder(TreeNode<Integer> root) {
            Queue<TreeNode<Integer>> que = new LinkedList<>();
            List<List<Integer>> list = new ArrayList<>();
            if(root!=null){
                que.add(root);
            }
            while(!que.isEmpty()){
                LinkedList<Integer> res = new LinkedList<>();
                for(int i =que.size();i>0;i--){
                    TreeNode<Integer> node = que.poll();
                    if(list.size()%2==0){
                        res.addLast(node.val);
                    }else{
                        res.addFirst(node.val);
                    }
                    if(node.left!=null){
                        que.add(node.left);
                    }
                    if(node.right!=null){
                        que.add(node.right);
                    }
                }
                list.add(res);
            }
            return list;
        }
    }

}
